package recursive;

/**
 * @author pengfei.hpf
 * @date 2020/3/7
 * @verdion 1.0.0
 * 698. 划分为k个相等的子集
 * 给定一个整数数组  nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。
 *
 * 示例 1：
 *
 * 输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4
 * 输出： True
 * 说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。
 *
 *
 * 注意:
 *
 * 1 <= k <= len(nums) <= 16
 * 0 < nums[i] < 10000
 *
 * 473. 火柴拼正方形 相似题目
 */
public class CanPartitionKSubsets {

    //TODO:  化整为零, 使用分组!!!
    public boolean canPartitionKSubsets(int[] nums, int k) {
        //???
        if(nums == null || nums.length == 0){
            return false;
        }

        int target = 0;
        for(int n: nums){
            target += n;
        }
        if(target %k != 0){
            return false;
        }
        target /= k;
        return canPar(nums, target, new int[k], 0);

    }
    private boolean canPar(int[] nums, int target, int[] sums, int index){
        if(index == nums.length){
            for(int i = 1; i < sums.length; i ++){
                if(sums[i] != sums[i -1]){
                    return false;
                }
            }
            return true;
        }
        for(int i = 0; i< sums.length; i ++){

            if(nums[index] + sums[i] <= target){
                sums[i] += nums[index];
                if(canPar(nums, target, sums, index + 1)){
                    return true;
                } else {
                    sums[i] -= nums[index];
                }
            }
        }
        return false;
    }
}
